/* 
   boyer-moore string search algorithm
   ref: http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
 */
#include <stdio.h>
#define max(a,b) (a<=b? (a):(b))
const char *bm(const char* s, const char* p)
{
  size_t len = strlen(p);
  int lsuffix[len], lchar[len];/* 该后缀和该字符上一次出现的位置 */
  int ocur[len];	       /* 所有出现该当前后缀的位置，计算lsuffix时使用的 */
  int i,j,skip;
  if (len == 0)
    return NULL;
  for (i = len-1; i>=0; --i){
    for (j = i-1; j >=0 && p[j] != p[i]; --j) { /*  */}
    lchar[i] = j;
    lsuffix[i] = -1;
  }
  for (i = len-1; i>=0; --i){
    ocur[i] = p[i] == p[len-1] ? 1 : 0;
    if (lsuffix[len-1] == -1 && ocur[i] && i != len-1)
      lsuffix[len-1] = i;
  }
  for (i=len-2; i>=0; --i) {
    for (j=0; j<i; ++j) {
      if (p[j] == p[i] && ocur[j+1]) {
	ocur[j] = 1;
	if (lsuffix[i] == -1)
	  lsuffix[i] = j;
      } else {
	ocur[j] = 0;
      }
    }
  }

  /* start search */
  skip = len-1;
  do {
    int skipchar, skipsuffix;
    while (skip-- && *s++) {}
    if (*s == '\0') 		/* reach end of string */
      return NULL;
    i = len-1;
    //printf("%s\n%s\n", s-i, p);
    while (*s == p[i] && i>=0) {
      i--;
      s--;
    }
    if (i == -1) 		/* found */
      return ++s;
    /* here have *s != p[i] */
    for (j = i-1; j>=0 && p[j]!=*s ;--j){}
    skipchar = j>=0 ? (i - j) : (i +1);
    if (i < len-1) {
      skipsuffix = i-1 - lsuffix[i-1];
      if (skipsuffix > skipchar) {
	skip = skipsuffix;
      }
    } else {
      skip = skipchar;
    }
    //printf("skip:%d\n", skip);    
  } while(1);
}
int main()
{
  char *s = "this is a sample example";
  char *p = "s";
  printf("\n\nresult:\n%s:%s\n%s\n",s,p,bm(s,p));
}
